package demo;

import java.util.Arrays;

public class ShellSort {
    //希尔排序

    private static void shellSort(int[]arr){
        //假设有10个元素就分5组
        int group= arr.length/2;
        //分组后循环对每个组内的元素进行插入排序
        while(true){
            insertSortWithGroup(arr,group);
            if(group==1){
                //如果只剩一组说明已经有序
                return;
            }
            //每次排序后再分组
            group=group/2;
        }
    }

    //希尔排序分组后对每一组的插入排序方法
    private static void insertSortWithGroup(int[]arr,int group){

        for(int i=group;i< arr.length;i++){
            int key=arr[i];
            int j=i-group;
            for( j=i-group;j>=0&&key<arr[j];j=j-group){
                arr[j+1]=arr[j];
            }
            arr[j+group]=key;
        }
    }

    public static void main(String[] args) {
        int[]arr={1,5,6,8,7,5,1,};
        shellSort(arr);
        System.out.println("希尔排序："+Arrays.toString(arr));
    }

}
